package airthmetic.exercise.string;

/**
 *
 * 680. 验证回文串 II
 * 简单
 * 相关标签
 * 相关企业
 * 给你一个字符串 s，最多 可以从中删除一个字符。
 *
 * 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aba"
 * 输出：true
 * 示例 2：
 *
 * 输入：s = "abca"
 * 输出：true
 * 解释：你可以删除字符 'c' 。
 * 示例 3：
 *
 * 输入：s = "abc"
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 105
 * s 由小写英文字母组成
 *
 */
public class _680_验证回文串II {
    public boolean validPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int left = 0;
        int right = s.length()-1;

        for(; left<right; left++, right--){
            if(charArray[left] != charArray[right]){
                //分两种情况，一是右边减一，二是左边加一
                return isPalindrome(charArray,left,right-1) || isPalindrome(charArray, left+1, right);
            }
        }
        return true;
    }

    public boolean isPalindrome(char[] charArray, int left, int right){
        while (left<right){
            if(charArray[left++] != charArray[right--]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        _680_验证回文串II v = new _680_验证回文串II();
        String s = "abca";
        String s2 = "aba";
        String s3 = "qpxtgkeljjdgecbvbfqommeveftxwflusjiyqjuntehhpdcrcvvcrcdphhetnujqyijsulfwxtfevemmoqfbvbcegdjjrlekgtxpq";
        System.out.println(v.validPalindrome(s));
        System.out.println(v.validPalindrome(s2));
        System.out.println(v.validPalindrome(s3));
    }




}
